/* 
  二分查找法: 非递归实现
 */

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function (nums, target) {
  let l = 0;
  let r = nums.length - 1;
  let mid;
  while (l <= r) {
    mid = l + Math.floor((r - l) / 2);
    if (nums[mid] === target) {
      return mid;
    } else if (nums[mid] > target) {
      r = mid - 1;
    } else {
      l = mid + 1;
    }
  }
  return -1;
};

// 递归实现
var search = function (nums, target) {
  const _search = (nums, l, r, target) => {
    // 结束条件
    if (l > r) {
      return -1;
    }
    const mid = l + Math.floor((r - l) / 2);

    if (nums[mid] === target) {
      return mid;
    } else if (nums[mid] > target) {
      r = mid - 1;
      return _search(nums, l, mid - 1, target);
    }
    return _search(nums, mid + 1, r, target);
  };

  return _search(nums, 0, nums.length - 1, target);
};

console.log(search([-1, 0, 3, 5, 9, 12], 9));
